import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        int[] nums = new int[]{-1, 0, 1, 2, -1, -4};
        Solution test = new Solution();
        test.threeSum(nums);
    }
}


class Solution
{
    public List<List<Integer>> threeSum(int[] nums)
    {
        List<List<Integer>> ret = new ArrayList<>();
        // 1. 排序
        Arrays.sort(nums);
        // 2. 利⽤双指针解决问题
        int n = nums.length;
        for(int i = 0; i < n; ) // 固定数 a
        {
            if(nums[i] > 0) break; // ⼩优化
            int left = i + 1, right = n - 1, target = -nums[i];
            while(left < right)
            {
                int sum = nums[left] + nums[right];
                if(sum > target) right--;
                else if(sum < target) left++;
                else{
                    // nums[i] nums[left] num[right]
                    ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],
                            nums[left], nums[right])));
                       left++; right--; // 缩⼩区间继续寻找
                       // 去重：left right
                       while(left < right && nums[left] == nums[left - 1]) left++;
                       while(left < right && nums[right] == nums[right + 1])
                            right--;
                }
            }
               // 去重：i
           i++;
           while(i < n && nums[i] == nums[i - 1]) i++;
        }
           return ret;
    }

//    public List<List<Integer>> threeSum(int[] nums) {
//        Arrays.sort(nums);
//
//        List<List<Integer>> ret = new ArrayList<>();
//
//        //定最外层的a
//        for (int a = 0; a < nums.length; ){
//            int b = a + 1;
//            int c = nums.length - 1;
//
//            //确定两个数是否等于前一个值的倒数
//            while (b < c){
//                if (nums[b] + nums[c] == -nums[a]){
//                    //list里面该怎么加？？？
//                    ret.add(new ArrayList<Integer>(Arrays.asList(nums[a],
//                            nums[b], nums[c])));
//
//                    //去重
//                    b++;
//                    c--;
//                    while (nums[b] == nums[b - 1]){
//                        b++;
//                    }
//
//                    while (nums[c] == nums[c + 1]){
//                        c--;
//                    }
//                }else if (nums[b] + nums[c] < -nums[a]){
//                    b++;
//                }else{
//                    c--;
//                }
//            }
//
//            //去重
//            a++;
//            while (a < nums.length && nums[a] == nums[a - 1]){
//                a++;
//            }
//        }
//
//        return ret;
//    }
}